class Solution {
    /**
     * 要点1：对所有的非叶子节点push_down
     * 要点2：index = tmp 注意要push_dows
     */
    public int[] sortArray(int[] nums) {
        // 对于所有非叶子结点 push_down
        for (int i = nums.length / 2; i >= 1; i--) {
            push_down(nums, i,nums.length);
        }
        // 将根节点拿出来，然后将最后一个节点放到根节点的位置，然后push_down
        int[] ans = new int[nums.length];
        int count = 0;
        for(int i=nums.length; i>=1; i--){
            ans[count++] = nums[0];
            nums[0] = nums[i-1];
            push_down(nums,1,i);
        }
        return ans;
    }

    public void push_down(int[] arr, int index,int length) {
        while (true) {
            int tmp = index, left = index << 1, right = (index << 1) + 1;
            if (left <= length && arr[left-1] < arr[tmp-1]) {
                tmp = left;
            }
            if (right <= length && arr[right-1] < arr[tmp-1]) {
                tmp = right;
            }
            if (tmp == index)
                break;
            else {
                int val = arr[index-1];
                arr[index-1] = arr[tmp-1];
                arr[tmp-1] = val;

                index = tmp;
            }
        }
    }
}